#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXSIZE 1024
#define NUL     '\0'

typedef struct 
{
    char data[MAXSIZE];
    int top;    //栈顶
} Stack;

/* 初始化栈 */
void init(Stack *st)
{
    st->top = -1;
}

/* 判空 */
int isEmpty(Stack *st)
{
    if(st->top == -1)
        return 1;
    return 0;
}

/* 判满 */
int isFull(Stack *st)
{
    if(st->top >= MAXSIZE)
        return 1;
    return 0;
}

/* 返回top值，不改变栈的结构 */
char getTop(Stack *st)
{
    if(isEmpty(st))
    {
        printf("栈为空\n");
        return NUL;
    }

    return st->data[st->top];
}

/* 出栈，返回栈顶数据 */
char pop(Stack *st)
{
    if(isEmpty(st))
    {
        printf("栈为空\n");
        return NUL;
    }

    return st->data[(st->top)--];
}

/* 入栈 */
void push(char c, Stack *st)
{
    if(isFull(st))
        printf("栈满\n");
    else
        st->data[++(st->top)] = c;
}

/* 输出栈中的数据 */
void show(Stack *st)
{
    while(st->top > -1)
        printf("%c, ", st->data[(st->top)--]);
    printf("\n");
}

/* 是否是操作符 */
int isOperate(char temp)
{
    if(temp=='+'||temp=='-'||temp=='*'||temp=='/'||temp=='('||temp==')'||temp=='#')
        return 1;
    return 0;
}

/* 是否有效字符 */
int isAvail(char temp)
{
    /* 如果temp既不是操作符和数值的话，则它是非法的 */
    if(isOperate(temp) || isdigit(temp))
        return 1;
    return 0;
}

/* 搜索矩阵位置 */
int detect(char temp)
{
    int i;
    char oper[7] = {'+','-','*','/','(',')','#'};
    
    for(i=0; i<7; i++)
    {
        if(temp == oper[i])
            return i;
    }
    
    return -1;
}

/* 判断优先级 */
char priority(char temp, char optr)
{
    /*
            + - * / ( ) #
            1 2 3 4 5 6 7
        + 1 < < < < > > > 
        - 2 < < < < > > >
        * 3 > > < < > > >
        / 4 > > < < > > > 
        ( 5 > > > > > = 0 
        ) 6 < < < < = 0 > 
        # 7 < < < < > 0 =
    */
    
    int row ,col;
    char priority[7][7]={
                            {'<','<','<','<','>','>','>'},
                            {'<','<','<','<','>','>','>'},
                            {'>','>','<','<','>','>','>'},
                            {'>','>','<','<','>','>','>'},
                            {'>','>','>','>','>','=','>'},
                            {'<','<','<','<','=','0','>'},
                            {'<','<','<','<','>','<','='}, 
                        };

    row = detect(temp);
    col = detect(optr); 
    
    return priority[row][col];
}

char evaluate(int a, int b, char oper)
{
    switch(oper)
    {
        case '+': return a+b+'0';
        case '-': return a-b+'0';
        case '*': return a*b+'0';
        case '/': return a/b+'0';
        default : return 0+'0';
    }
}

/* 计算表达式 */
int calculateExpress(char *express)
{
    int result=0;
    int a,b;
    Stack OPTR,OPND;    /* OPTR存储操作符，OPND操作数值 */

    init(&OPTR);
    init(&OPND);
    push('#',&OPTR);    /* 默认第一个位'#' */

    ////////////////////-算法-////////////////////////////

    while(*express != '\0')
    {
        char temp = *(express); 
        
        printf("---------------------------------\n");
        printf("当前的符号为%c\n", temp);
        
        if(isAvail(temp))               /* 是否是有效字符 */
        { 
                if(isOperate(temp))    /* 输入的是操作符 */
                {
                    char oper,result;
                    char optr = getTop(&OPTR);              /* 栈中top位的操作符 */

                    printf("栈顶操作符位：%c\n", optr);
                    char prior = priority(temp, optr);      /* 判断优先级 */

                    switch(prior)
                    {
                        case '>':
                                    push(temp,&OPTR);
                                    printf("将符号位%c入栈\n",temp);
                                    express++;
                                    break;
                        case '<':
                                    a = pop(&OPND)-'0';     /* 存在栈中的都是char字符 */
                                    b = pop(&OPND)-'0';
                                    oper = pop(&OPTR);
                                    result = evaluate(b, a, oper);  /* 出栈一个操作符，计算结果 */
                                    push(result,&OPND);             /* 结果入OPND */
                                    printf("%d%c%d结果为:%d\n",b,oper,a,result-'0');
                                    break;
                        case '=':
                                    pop(&OPTR);
                                    printf("消除括号\n");
                                    express++;
                                    break;
                    }
                }
                
                if(isdigit(temp))           /* 输入的是数值 */
                {
                    push(temp,&OPND);       /* 将数值位入栈 */
                    express++;
                    printf("将数值%c压入栈\n",temp);
                }
        }
        else
        {
            printf("表达式中有非法字符\n");
            exit(-1);
        }
    }

    return getTop(&OPND)-'0';
}

/* 输入表达式 */
void inputExpress(char *express)
{
    int len;
    
    printf("请输入一个表达式:");
    scanf("%s",express);
    
    len = strlen(express);
    express[len]='#';   /* 表达式最后一位默认为'#' */
    express[len+1]='\0';
}

/* 输出表达式 */
void output(char *express,  int result)
{
    int i = 0;
    
    printf("---------------------------------\n表达式:");
    while(express[i] != '#')
    {
        printf("%c",express[i]);
        i++;
    }
    printf("=%d\n",result);
}

int main()
{
    char express[100]; 
    int result = 0;
    
    inputExpress(express);              /* 输入表达式 */
    result = calculateExpress(express); /* 计算表达式 */
    output(express,result);             /* 输出表达式 */

    return 0;
}
